home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2004 April / Gamestar_61_2004-04_dvdb.iso / DVDStar / Editace / hltp.exe / {app} / Source Code / Textures SDK / common / polylib.c < prev    next >
C/C++ Source or Header  |  1998-12-02  |  14KB  |  709 lines
  1. /***
  2. *
  3. *    Copyright (c) 1998, Valve LLC. All rights reserved.
  4. *    
  5. *    This product contains software technology licensed from Id 
  6. *    Software, Inc. ("Id Technology").  Id Technology (c) 1996 Id Software, Inc. 
  7. *    All Rights Reserved.
  8. *
  9. ****/
  10.  
  11.  
  12. #include "cmdlib.h"
  13. #include "mathlib.h"
  14. #include "polylib.h"
  15.  
  16. int    c_active_windings;
  17. int    c_peak_windings;
  18. int    c_winding_allocs;
  19. int    c_winding_points;
  20.  
  21. #define    BOGUS_RANGE    8192
  22.  
  23. void pw(winding_t *w)
  24. {
  25.     int        i;
  26.     for (i=0 ; i<w->numpoints ; i++)
  27.         printf ("(%5.1f, %5.1f, %5.1f)\n",w->p[i][0], w->p[i][1],w->p[i][2]);
  28. }
  29.  
  30.  
  31. /*
  32. =============
  33. AllocWinding
  34. =============
  35. */
  36. winding_t    *AllocWinding (int points)
  37. {
  38.     winding_t    *w;
  39.     int            s;
  40.  
  41.     c_winding_allocs++;
  42.     c_winding_points += points;
  43.     c_active_windings++;
  44.     if (c_active_windings > c_peak_windings)
  45.         c_peak_windings = c_active_windings;
  46.     s = sizeof(vec_t)*3*points + sizeof(int);
  47.     s += sizeof(vec_t) - sizeof(w->numpoints);        // padding
  48.  
  49.     w = malloc (s);
  50.     memset (w, 0, s); 
  51.  
  52.     return w;
  53. }
  54.  
  55. void FreeWinding (winding_t *w)
  56. {
  57.     c_active_windings--;
  58.     free (w);
  59. }
  60.  
  61. /*
  62. ============
  63. RemoveColinearPoints
  64. ============
  65. */
  66. int    c_removed;
  67.  
  68. void    RemoveColinearPoints (winding_t *w)
  69. {
  70.     int        i, j, k;
  71.     vec3_t    v1, v2;
  72.     int        nump;
  73.     vec3_t    p[MAX_POINTS_ON_WINDING];
  74.  
  75.     nump = 0;
  76.     for (i=0 ; i<w->numpoints ; i++)
  77.     {
  78.         j = (i+1)%w->numpoints;
  79.         k = (i+w->numpoints-1)%w->numpoints;
  80.         VectorSubtract (w->p[j], w->p[i], v1);
  81.         VectorSubtract (w->p[i], w->p[k], v2);
  82.         VectorNormalize(v1);
  83.         VectorNormalize(v2);
  84.         if (DotProduct(v1, v2) < 1.0-ON_EPSILON)
  85.         {
  86.             VectorCopy (w->p[i], p[nump]);
  87.             nump++;
  88.         }
  89.     }
  90.  
  91.     if (nump == w->numpoints)
  92.         return;
  93.  
  94.     c_removed += w->numpoints - nump;
  95.     w->numpoints = nump;
  96.     memcpy (w->p, p, nump*sizeof(p[0]));
  97. }
  98.  
  99. /*
  100. ============
  101. WindingPlane
  102. ============
  103. */
  104. void WindingPlane (winding_t *w, vec3_t normal, vec_t *dist)
  105. {
  106.     vec3_t    v1, v2;
  107.  
  108.     VectorSubtract (w->p[1], w->p[0], v1);
  109.     VectorSubtract (w->p[2], w->p[0], v2);
  110.     CrossProduct (v2, v1, normal);
  111.     VectorNormalize (normal);
  112.     *dist = DotProduct (w->p[0], normal);
  113.  
  114. }
  115.  
  116. /*
  117. =============
  118. WindingArea
  119. =============
  120. */
  121. vec_t    WindingArea (winding_t *w)
  122. {
  123.     int        i;
  124.     vec3_t    d1, d2, cross;
  125.     vec_t    total;
  126.  
  127.     total = 0;
  128.     for (i=2 ; i<w->numpoints ; i++)
  129.     {
  130.         VectorSubtract (w->p[i-1], w->p[0], d1);
  131.         VectorSubtract (w->p[i], w->p[0], d2);
  132.         CrossProduct (d1, d2, cross);
  133.         total += 0.5 * VectorLength ( cross );
  134.     }
  135.     return total;
  136. }
  137.  
  138. void    WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs)
  139. {
  140.     vec_t    v;
  141.     int        i,j;
  142.  
  143.     mins[0] = mins[1] = mins[2] = 99999;
  144.     maxs[0] = maxs[1] = maxs[2] = -99999;
  145.  
  146.     for (i=0 ; i<w->numpoints ; i++)
  147.     {
  148.         for (j=0 ; j<3 ; j++)
  149.         {
  150.             v = w->p[i][j];
  151.             if (v < mins[j])
  152.                 mins[j] = v;
  153.             if (v > maxs[j])
  154.                 maxs[j] = v;
  155.         }
  156.     }
  157. }
  158.  
  159. /*
  160. =============
  161. WindingCenter
  162. =============
  163. */
  164. void    WindingCenter (winding_t *w, vec3_t center)
  165. {
  166.     int        i;
  167.     vec3_t    d1, d2, cross;
  168.     float    scale;
  169.  
  170.     VectorCopy (vec3_origin, center);
  171.     for (i=0 ; i<w->numpoints ; i++)
  172.         VectorAdd (w->p[i], center, center);
  173.  
  174.     scale = 1.0/w->numpoints;
  175.     VectorScale (center, scale, center);
  176. }
  177.  
  178. /*
  179. =================
  180. BaseWindingForPlane
  181. =================
  182. */
  183. winding_t *BaseWindingForPlane (vec3_t normal, float dist)
  184. {
  185.     int        i, x;
  186.     vec_t    max, v;
  187.     vec3_t    org, vright, vup;
  188.     winding_t    *w;
  189.     
  190. // find the major axis
  191.  
  192.     max = -BOGUS_RANGE;
  193.     x = -1;
  194.     for (i=0 ; i<3; i++)
  195.     {
  196.         v = fabs(normal[i]);
  197.         if (v > max)
  198.         {
  199.             x = i;
  200.             max = v;
  201.         }
  202.     }
  203.     if (x==-1)
  204.         Error ("BaseWindingForPlane: no axis found");
  205.         
  206.     VectorCopy (vec3_origin, vup);    
  207.     switch (x)
  208.     {
  209.     case 0:
  210.     case 1:
  211.         vup[2] = 1;
  212.         break;        
  213.     case 2:
  214.         vup[0] = 1;
  215.         break;        
  216.     }
  217.  
  218.     v = DotProduct (vup, normal);
  219.     VectorMA (vup, -v, normal, vup);
  220.     VectorNormalize (vup);
  221.         
  222.     VectorScale (normal, dist, org);
  223.     
  224.     CrossProduct (vup, normal, vright);
  225.     
  226.     VectorScale (vup, 9000, vup);
  227.     VectorScale (vright, 9000, vright);
  228.  
  229. // project a really big    axis aligned box onto the plane
  230.     w = AllocWinding (4);
  231.     
  232.     VectorSubtract (org, vright, w->p[0]);
  233.     VectorAdd (w->p[0], vup, w->p[0]);
  234.     
  235.     VectorAdd (org, vright, w->p[1]);
  236.     VectorAdd (w->p[1], vup, w->p[1]);
  237.     
  238.     VectorAdd (org, vright, w->p[2]);
  239.     VectorSubtract (w->p[2], vup, w->p[2]);
  240.     
  241.     VectorSubtract (org, vright, w->p[3]);
  242.     VectorSubtract (w->p[3], vup, w->p[3]);
  243.  
  244.     w->numpoints = 4;
  245.     
  246.     return w;    
  247. }
  248.  
  249. /*
  250. ==================
  251. CopyWinding
  252. ==================
  253. */
  254. winding_t    *CopyWinding (winding_t *w)
  255. {
  256.     int            size;
  257.     winding_t    *c;
  258.     
  259.     size = (int)((winding_t *)0)->p[w->numpoints];
  260.     c = malloc (size);
  261.     memcpy (c, w, size);
  262.     return c;
  263. }
  264.  
  265.  
  266. /*
  267. =============
  268. ClipWinding
  269. =============
  270. */
  271. void    ClipWinding (winding_t *in, vec3_t normal, vec_t dist,
  272.                      winding_t **front, winding_t **back)
  273. {
  274.     vec_t    dists[MAX_POINTS_ON_WINDING+4];
  275.     int        sides[MAX_POINTS_ON_WINDING+4];
  276.     int        counts[3];
  277.     vec_t    dot;
  278.     int        i, j;
  279.     vec_t    *p1, *p2;
  280.     vec3_t    mid;
  281.     winding_t    *f, *b;
  282.     int        maxpts;
  283.     
  284.     counts[0] = counts[1] = counts[2] = 0;
  285.  
  286. // determine sides for each point
  287.     for (i=0 ; i<in->numpoints ; i++)
  288.     {
  289.         dot = DotProduct (in->p[i], normal);
  290.         dot -= dist;
  291.         dists[i] = dot;
  292.         if (dot > ON_EPSILON)
  293.             sides[i] = SIDE_FRONT;
  294.         else if (dot < -ON_EPSILON)
  295.             sides[i] = SIDE_BACK;
  296.         else
  297.         {
  298.             sides[i] = SIDE_ON;
  299.         }
  300.         counts[sides[i]]++;
  301.     }
  302.     sides[i] = sides[0];
  303.     dists[i] = dists[0];
  304.     
  305.     *front = *back = NULL;
  306.  
  307.     if (!counts[0])
  308.     {
  309.         *back = CopyWinding (in);
  310.         return;
  311.     }
  312.     if (!counts[1])
  313.     {
  314.         *front = CopyWinding (in);
  315.         return;
  316.     }
  317.  
  318.     maxpts = in->numpoints+4;    // can't use counts[0]+2 because
  319.                                 // of fp grouping errors
  320.  
  321.     *front = f = AllocWinding (maxpts);
  322.     *back = b = AllocWinding (maxpts);
  323.         
  324.     for (i=0 ; i<in->numpoints ; i++)
  325.     {
  326.         p1 = in->p[i];
  327.         
  328.         if (sides[i] == SIDE_ON)
  329.         {
  330.             VectorCopy (p1, f->p[f->numpoints]);
  331.             f->numpoints++;
  332.             VectorCopy (p1, b->p[b->numpoints]);
  333.             b->numpoints++;
  334.             continue;
  335.         }
  336.     
  337.         if (sides[i] == SIDE_FRONT)
  338.         {
  339.             VectorCopy (p1, f->p[f->numpoints]);
  340.             f->numpoints++;
  341.         }
  342.         if (sides[i] == SIDE_BACK)
  343.         {
  344.             VectorCopy (p1, b->p[b->numpoints]);
  345.             b->numpoints++;
  346.         }
  347.  
  348.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  349.             continue;
  350.             
  351.     // generate a split point
  352.         p2 = in->p[(i+1)%in->numpoints];
  353.         
  354.         dot = dists[i] / (dists[i]-dists[i+1]);
  355.         for (j=0 ; j<3 ; j++)
  356.         {    // avoid round off error when possible
  357.             if (normal[j] == 1)
  358.                 mid[j] = dist;
  359.             else if (normal[j] == -1)
  360.                 mid[j] = -dist;
  361.             else
  362.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  363.         }
  364.             
  365.         VectorCopy (mid, f->p[f->numpoints]);
  366.         f->numpoints++;
  367.         VectorCopy (mid, b->p[b->numpoints]);
  368.         b->numpoints++;
  369.     }
  370.     
  371.     if (f->numpoints > maxpts || b->numpoints > maxpts)
  372.         Error ("ClipWinding: points exceeded estimate");
  373.     if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
  374.         Error ("ClipWinding: MAX_POINTS_ON_WINDING");
  375. }
  376.  
  377.  
  378.  
  379. /*
  380. =============
  381. ClipWindingNoCopy
  382. =============
  383. */
  384. void    ClipWindingNoCopy (winding_t *in, vec3_t normal, vec_t dist,
  385.                      winding_t **front, winding_t **back)
  386. {
  387.     vec_t    dists[MAX_POINTS_ON_WINDING+4];
  388.     int        sides[MAX_POINTS_ON_WINDING+4];
  389.     int        counts[3];
  390.     vec_t    dot;
  391.     int        i, j;
  392.     vec_t    *p1, *p2;
  393.     vec3_t    mid;
  394.     winding_t    *f, *b;
  395.     int        maxpts;
  396.     
  397.     counts[0] = counts[1] = counts[2] = 0;
  398.  
  399. // determine sides for each point
  400.     for (i=0 ; i<in->numpoints ; i++)
  401.     {
  402.         dot = DotProduct (in->p[i], normal);
  403.         dot -= dist;
  404.         dists[i] = dot;
  405.         if (dot > ON_EPSILON)
  406.             sides[i] = SIDE_FRONT;
  407.         else if (dot < -ON_EPSILON)
  408.             sides[i] = SIDE_BACK;
  409.         else
  410.         {
  411.             sides[i] = SIDE_ON;
  412.         }
  413.         counts[sides[i]]++;
  414.     }
  415.     sides[i] = sides[0];
  416.     dists[i] = dists[0];
  417.     
  418.     *front = *back = NULL;
  419.  
  420.     if (!counts[0])
  421.     {
  422.         *back = in;
  423.         return;
  424.     }
  425.     if (!counts[1])
  426.     {
  427.         *front = in;
  428.         return;
  429.     }
  430.  
  431.     maxpts = in->numpoints+4;    // can't use counts[0]+2 because
  432.                                 // of fp grouping errors
  433.  
  434.     *front = f = AllocWinding (maxpts);
  435.     *back = b = AllocWinding (maxpts);
  436.         
  437.     for (i=0 ; i<in->numpoints ; i++)
  438.     {
  439.         p1 = in->p[i];
  440.         
  441.         if (sides[i] == SIDE_ON)
  442.         {
  443.             VectorCopy (p1, f->p[f->numpoints]);
  444.             f->numpoints++;
  445.             VectorCopy (p1, b->p[b->numpoints]);
  446.             b->numpoints++;
  447.             continue;
  448.         }
  449.     
  450.         if (sides[i] == SIDE_FRONT)
  451.         {
  452.             VectorCopy (p1, f->p[f->numpoints]);
  453.             f->numpoints++;
  454.         }
  455.         if (sides[i] == SIDE_BACK)
  456.         {
  457.             VectorCopy (p1, b->p[b->numpoints]);
  458.             b->numpoints++;
  459.         }
  460.  
  461.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  462.             continue;
  463.             
  464.     // generate a split point
  465.         p2 = in->p[(i+1)%in->numpoints];
  466.         
  467.         dot = dists[i] / (dists[i]-dists[i+1]);
  468.         for (j=0 ; j<3 ; j++)
  469.         {    // avoid round off error when possible
  470.             if (normal[j] == 1)
  471.                 mid[j] = dist;
  472.             else if (normal[j] == -1)
  473.                 mid[j] = -dist;
  474.             else
  475.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  476.         }
  477.             
  478.         VectorCopy (mid, f->p[f->numpoints]);
  479.         f->numpoints++;
  480.         VectorCopy (mid, b->p[b->numpoints]);
  481.         b->numpoints++;
  482.     }
  483.     
  484.     if (f->numpoints > maxpts || b->numpoints > maxpts)
  485.         Error ("ClipWinding: points exceeded estimate");
  486.     if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
  487.         Error ("ClipWinding: MAX_POINTS_ON_WINDING");
  488. }
  489.  
  490.  
  491. /*
  492. =============
  493. ChopWindingNoFree
  494. =============
  495. */
  496. winding_t    *ChopWindingNoFree (winding_t *in, vec3_t normal, vec_t dist)
  497. {
  498.     vec_t    dists[MAX_POINTS_ON_WINDING+4];
  499.     int        sides[MAX_POINTS_ON_WINDING+4];
  500.     int        counts[3];
  501.     vec_t    dot;
  502.     int        i, j;
  503.     vec_t    *p1, *p2;
  504.     vec3_t    mid;
  505.     winding_t    *f;
  506.     int        maxpts;
  507.  
  508.     counts[0] = counts[1] = counts[2] = 0;
  509.  
  510. // determine sides for each point
  511.     for (i=0 ; i<in->numpoints ; i++)
  512.     {
  513.         dot = DotProduct (in->p[i], normal);
  514.         dot -= dist;
  515.         dists[i] = dot;
  516.         if (dot > ON_EPSILON)
  517.             sides[i] = SIDE_FRONT;
  518.         else if (dot < -ON_EPSILON)
  519.             sides[i] = SIDE_BACK;
  520.         else
  521.         {
  522.             sides[i] = SIDE_ON;
  523.         }
  524.         counts[sides[i]]++;
  525.     }
  526.     sides[i] = sides[0];
  527.     dists[i] = dists[0];
  528.     
  529.     if (!counts[0])
  530.         return NULL;
  531.     if (!counts[1])
  532.         return in;
  533.  
  534.     maxpts = in->numpoints+4;    // can't use counts[0]+2 because
  535.                                 // of fp grouping errors
  536.  
  537.     f = AllocWinding (maxpts);
  538.         
  539.     for (i=0 ; i<in->numpoints ; i++)
  540.     {
  541.         p1 = in->p[i];
  542.         
  543.         if (sides[i] == SIDE_ON)
  544.         {
  545.             VectorCopy (p1, f->p[f->numpoints]);
  546.             f->numpoints++;
  547.             continue;
  548.         }
  549.     
  550.         if (sides[i] == SIDE_FRONT)
  551.         {
  552.             VectorCopy (p1, f->p[f->numpoints]);
  553.             f->numpoints++;
  554.         }
  555.  
  556.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  557.             continue;
  558.             
  559.     // generate a split point
  560.         p2 = in->p[(i+1)%in->numpoints];
  561.         
  562.         dot = dists[i] / (dists[i]-dists[i+1]);
  563.         for (j=0 ; j<3 ; j++)
  564.         {    // avoid round off error when possible
  565.             if (normal[j] == 1)
  566.                 mid[j] = dist;
  567.             else if (normal[j] == -1)
  568.                 mid[j] = -dist;
  569.             else
  570.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  571.         }
  572.             
  573.         VectorCopy (mid, f->p[f->numpoints]);
  574.         f->numpoints++;
  575.     }
  576.     
  577.     if (f->numpoints > maxpts)
  578.         Error ("ClipWinding: points exceeded estimate");
  579.     if (f->numpoints > MAX_POINTS_ON_WINDING)
  580.         Error ("ClipWinding: MAX_POINTS_ON_WINDING");
  581.  
  582.     return f;
  583. }
  584.  
  585.  
  586. /*
  587. =================
  588. ChopWinding
  589.  
  590. Returns the fragment of in that is on the front side
  591. of the cliping plane.  The original is freed.
  592. =================
  593. */
  594. winding_t    *ChopWinding (winding_t *in, vec3_t normal, vec_t dist)
  595. {
  596.     winding_t    *f, *b;
  597.  
  598.     ClipWinding (in, normal, dist, &f, &b);
  599.     FreeWinding (in);
  600.     if (b)
  601.         FreeWinding (b);
  602.     return f;
  603. }
  604.  
  605.  
  606. /*
  607. =================
  608. CheckWinding
  609.  
  610. =================
  611. */
  612. void CheckWinding (winding_t *w)
  613. {
  614.     int        i, j;
  615.     vec_t    *p1, *p2;
  616.     vec_t    d, edgedist;
  617.     vec3_t    dir, edgenormal, facenormal;
  618.     vec_t    area;
  619.     vec_t    facedist;
  620.  
  621.     if (w->numpoints < 3)
  622.         Error ("CheckWinding: %i points",w->numpoints);
  623.     
  624.     area = WindingArea(w);
  625.     if (area < 1)
  626.         Error ("CheckWinding: %f area", area);
  627.  
  628.     WindingPlane (w, facenormal, &facedist);
  629.     
  630.     for (i=0 ; i<w->numpoints ; i++)
  631.     {
  632.         p1 = w->p[i];
  633.  
  634.         for (j=0 ; j<3 ; j++)
  635.             if (p1[j] > BOGUS_RANGE || p1[j] < -BOGUS_RANGE)
  636.                 Error ("CheckFace: BUGUS_RANGE: %f",p1[j]);
  637.  
  638.         j = i+1 == w->numpoints ? 0 : i+1;
  639.         
  640.     // check the point is on the face plane
  641.         d = DotProduct (p1, facenormal) - facedist;
  642.         if (d < -ON_EPSILON || d > ON_EPSILON)
  643.             Error ("CheckWinding: point off plane");
  644.     
  645.     // check the edge isn't degenerate
  646.         p2 = w->p[j];
  647.         VectorSubtract (p2, p1, dir);
  648.         
  649.         if (VectorLength (dir) < ON_EPSILON)
  650.             Error ("CheckWinding: degenerate edge");
  651.             
  652.         CrossProduct (facenormal, dir, edgenormal);
  653.         VectorNormalize (edgenormal);
  654.         edgedist = DotProduct (p1, edgenormal);
  655.         edgedist += ON_EPSILON;
  656.         
  657.     // all other points must be on front side
  658.         for (j=0 ; j<w->numpoints ; j++)
  659.         {
  660.             if (j == i)
  661.                 continue;
  662.             d = DotProduct (w->p[j], edgenormal);
  663.             if (d > edgedist)
  664.                 Error ("CheckWinding: non-convex");
  665.         }
  666.     }
  667. }
  668.  
  669.  
  670. /*
  671. ============
  672. WindingOnPlaneSide
  673. ============
  674. */
  675. int        WindingOnPlaneSide (winding_t *w, vec3_t normal, vec_t dist)
  676. {
  677.     qboolean    front, back;
  678.     int            i;
  679.     vec_t        d;
  680.  
  681.     front = false;
  682.     back = false;
  683.     for (i=0 ; i<w->numpoints ; i++)
  684.     {
  685.         d = DotProduct (w->p[i], normal) - dist;
  686.         if (d < -ON_EPSILON)
  687.         {
  688.             if (front)
  689.                 return SIDE_CROSS;
  690.             back = true;
  691.             continue;
  692.         }
  693.         if (d > ON_EPSILON)
  694.         {
  695.             if (back)
  696.                 return SIDE_CROSS;
  697.             front = true;
  698.             continue;
  699.         }
  700.     }
  701.  
  702.     if (back)
  703.         return SIDE_BACK;
  704.     if (front)
  705.         return SIDE_FRONT;
  706.     return SIDE_ON;
  707. }
  708.  
  709.